Variaciones, Permutaciones y Combinaciones

VARIACIONES,
PERMUTACIONES Y
COMBINACIONES

“La ciencia de la combinación es una música del pensamiento puro, en la que el alfabeto ocupa el lugar de la gama musical” (Ramon Llull)

Variaciones y Permutaciones, sin Repetición
Generación

Tenemos una secuencia x de longitud n. Llamando var(x m) a las variaciones de los elementos de x tomados de m en m, siendo (1 ≤ m ≤ n), se tiene:

⟨( var(x 1) = x )⟩
var(x m) se calcula a partir de var(x m−1) de la manera siguiente:
1. Inicialmente, var(x m) es la secuencia vacía.
2. Se recorren los elementos z de var(x m−1).
3. Se recorren los elementos y de x. Si y no pertenece a z, se añade a var(x m) el elemento unión de z e y.

Ejemplo con (x = 1234):

m	Proceso
1	1			2			3			4
2	12	13	14	21	23	24	31	32	34	41	42	43
3	123 124	132 134	142 143	213 214	231 234	241 243	312 314	321 324	341 342	412 413	421 423	431 432
4	1234 1243	1324 1342	1423 1432	2134 2143	2314 2341	2413 2431	3124 3142	3214 3241	3412 3421	4123 4132	4213 4231	4312 4321

Algoritmo


⟨( var(x m) = (¡x ← m=1 →' (res=()


                ([(z=[(var(x m−1))↓] y=[x↓]


                 x∉z → (res° = (res↓ (z↓ y↓)))])


                 ¡res)! )⟩

Ejemplos

var((a b c d) 1) // ev. ( a b c d ) ev. abcd
var(( 1…20 ) 1) // ev. ( 1…20 )
(x = ( 1…4 ) var(x 2) // ev. ( 12 13 14 21 23 24 31 32 34 41 42 43 )
(x = (a b c d) var(x 2) // ev. ( ab ac ad ba bc bd ca cb cd da db dc )
(x = (a b c) var(x 3) // ev. ( abc acb bac bca cab cba )
(x = ( 1…4 ) var(x 3) // ev. ( 123 124 132 134 142 143 213 214 231 234 // 241 243 312 314 321 324 341 342 412 413 // 421 423 431 432 )
(x = ( 1…4 ) var(4 4) // ev. ( 1234 1243 1324 1342 1423 1432 2134 2143 // 2314 2341 2413 2431 3124 3142 3214 3241 // 3412 3421 4123 4132 4213 4231 4312 4321 )

Permutaciones

Cuando m = x#, tenemos las permutaciones de los elementos de x:

⟨( per(x) = var(x x#) )⟩

Número de elementos

El número de elementos de var(x m) es:

⟨( (var(x m))# = (n*…*(n−m+1))/(n = x#) )⟩

Si m=n, tenemos el número de permutaciones de n elementos:

⟨( per(x))# = (x#)*…*1 )⟩ // factorial del núm. de elementos de x

Ejemplos con (x = (a b c d)):

(var(x 1))# // ev. 4
(var(x 2))# // ev. 4*3 ev. 12
(var(x 3))# // ev. 4*3*2 ev. 24
(var(x 4))# // ev. 4*3*2*1 ev. 24
(per(x))# // ev. 4*3*2*1 ev. 24

Variaciones y Permutaciones, con Repetición
Generación

Si tenemos la secuencia x de n elementos a1, … , an, es decir, (x = a1…an), las variaciones con repetición de estos n elementos tomados de m en m (1 ≤ m ≤ n), que podemos simbolizar por vr(x m), es:

⟨( vr(x m) = ([([x↓]★m)]) )⟩

Ejemplos

(x = (a b)) // eq. (x = ab) vr(x 1) // ev. ([([a b])]) ev. ((a b)) ev. ab vr(x 2) // ev. ([([a b]★2)]) rep. ([([a b] [a b])]) // rep. ((a a) (a b) (b a) (b b)) eq. (aa ab ba bb)
(x = (a b c)) vr(x 1) // ev. ([([a b c])]) ev. ([([a b c])]) // ev. ((a b c)) ev. Abc vr(x 2) // ev. ([([a b c]★2)]) rep. ([([a b c] [a b c])]) // rep. ((a a) (a b) (a c) (b a) (b b) (b c) // (c a) (c b) (c c)) eq. // (aa ab ac ba bb bc ca cb cc) vr(x 3) // ev. ([([a b c]★3)]) rep. (aaa aab aac aba abb abc aca acb acc (baa bab bac bba bbb bbc bca bcb bcc (caa cab cac cba cbb cbc cca ccb ccc)

Permutaciones con repetición

Si (m = x#), tenemos las permutaciones con repetición, pr(x):

⟨( pr(x) = ([([x↓]★(x#))]) )⟩

Número de elementos

El número de elementos es n^m, es decir,

⟨( (vr(x m))# = (x#)^m )⟩

Si (m = x#), tenemos el número de permutaciones con repetición:

⟨( pr(x))# = (x#)^(x#) )⟩ eq. ⟨( pr(x))# = (x#)(^^)2 )⟩

Combinaciones
Generación

Tenemos una secuencia x de longitud n. Llamando comb(x m) al conjunto formado por los conjuntos de los elementos de x tomados de m en m (1 ≤ m ≤ n), se tiene:

⟨( comb(x 1) = {[{[x↓]}]} )⟩

comb(x m) se calcula a partir de comb(x m−1) de la manera siguiente:

Inicialmente, la respuesta (res) es el conjunto vacío.
Se recorren los conjuntos z de comb(x m−1).
Se recorren los elementos y de x.
Si y∈z, calcular w = z∪{y}
Si w∉res, entonces añadir w a res.
Devolver res como resultado.

Ejemplo con n=4:

m	Proceso
1	{1}			{2}		{3}	{4}
2	{1 2}		{1 3}	{1 4}	{2 3}	{2 4}	{3 4}
3	{1 2 3}	{1 2 4}	{1 3 4}		{2 3 4}
4	{1 2 3 4}

Algoritmo


⟨( comb(x m) = (¡{[{[x↓]}]} ← m=1 →’ (res={}


                [z=[(comb(x m−1))↓] y=[x↓]


                 (y∈z → (w = z∪{y})


                 (w∉res → (res° = (res∪w))]


                 ¡res)! )⟩

Ejemplos

Si x=(1 2 3 4),

comb(x 1) // ev. { {1} {2} {3} {4} }
comb(x 2) // ev. { {1 2} {1 3} {1 4} {2 3} {2 4} {3 4} }
comb(x 3) // ev. { 123 124 134 }
comb(x 4) // ev. { {1 2 3 4} }

Número de elementos

⟨( (comb(x m))# = (var(x m)# ÷ per(x)# )⟩

Ejemplos:

comb(4 1)# // ev. 4
comb(4 2)# // ev. (4*3)(1*2) ev. 6
comb(4 3)# // ev. (4*3*2)÷(1*2*3) ev. 4
comb(4 4)# // ev. (4*3*2*1)÷(1*2*3*4) ev. 1

Propiedades

⟨( comb(n m)# = (comb(n−1 m−1)# + comb(n−1 m)#) )⟩